package LeetCodeHot100TopInterview;

public class Q034_FindFirstAndLastInSortArray {
    //二分查找 ==> 找到大于/等于/小于某个数最左/右的位置
    public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0){
            return new int[]{-1,-1};
        }
        int leftIndex = find_left(nums, target);
        int rightIndex = find_right(nums, target);
        return new int[]{leftIndex, rightIndex};
    }

    //找到等于某个数最左位置
    public int find_left(int[] nums, int target){
        int left = 0;
        int right = nums.length - 1;
        int mid = -1;
        int ans = -1;
        while (left <= right){
            mid = left + ((right - left) >> 2);
            if (nums[mid] == target) {
                ans = mid;
                right = mid - 1;
            }else if (nums[mid] > target){
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return ans;
    }

    //找到等于某个数最右位置
    public int find_right(int[] nums, int target){
        int left = 0;
        int right = nums.length - 1;
        int mid = -1;
        int ans = -1;
        while (left <= right){
            mid = left + ((right - left) >> 2);
            if (nums[mid] == target) {
                ans = mid;
                left = mid + 1;
            }else if (nums[mid] > target){
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Q034_FindFirstAndLastInSortArray fun = new Q034_FindFirstAndLastInSortArray();
        System.out.println(fun.searchRange(new int[]{1}, 8));
    }
}
